package com.it.od.manual;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author: liminghui
 * @date: 2024/3/28 19:01
 * @version: 1.0
 * @description: 二面笔试题    笔试题：
 * [背包问题]有一个背包，背包容量是M（150）。有K（7）个物品，物品可以是任意重量/价值。
 * 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
 * 测试用例1：
 * M=30, K=3
 * 物品 A B C
 * 重量 28 12 12
 * 价值 30 20 20
 * 答案是: BC
 * 30
 * 3
 * A B C
 * 28 12 12
 * 50 20 20
 * <p>
 * 测试用例2：
 * M=150, K=7
 * 物品 A B C D E F G
 * 重量 35 30 60 50 40 10 25
 * 价值 10 40 30 50 35 40 30
 */
public class BeiBao {
    public static int maxValue = 0;
    public static int m = 0;
    public static String res;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = Integer.parseInt(sc.nextLine());
        int k = Integer.parseInt(sc.nextLine());
        int[] goods = Arrays.stream(sc.nextLine().split("\\s+")).mapToInt(x -> x.charAt(0) - 'A').toArray();
        int[] weights = Arrays.stream(sc.nextLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
        int[] values = Arrays.stream(sc.nextLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
        int[][] matrix = new int[k][3];

        for (int i = 0; i < goods.length; i++) {
            matrix[i][0] = goods[i];
        }
        for (int i = 0; i < weights.length; i++) {
            matrix[i][1] = weights[i];
        }
        for (int i = 0; i < values.length; i++) {
            matrix[i][2] = values[i];
        }

        List<Integer> candidate = new ArrayList<>();
        dfs(matrix, candidate, 0);
        System.out.println(res);
    }

    // 顺序有关系，就全排列，用Used[i]标记是否已使用
    // 组合就用idx控制，每次往后选。、
    private static void dfs(int[][] matrix, List<Integer> candidate, int idx) {
        // 计算总重量  // 计算总价值
        int sum0fWeight = 0;
        int sum0fValue = 0;
        for (Integer item : candidate) {
            sum0fWeight += matrix[item][1];
            sum0fValue += matrix[item][2];
        }

        if (sum0fWeight > m) {
            return;
        }
        if (sum0fValue > maxValue) {
            maxValue = sum0fValue;
            StringBuilder sb = new StringBuilder();
            for (Integer element : candidate) {
                sb.append((char) (element + 'A'));
            }
            res = sb.toString();
        }

        for (int i = idx; i < matrix.length; i++) {
            candidate.add(matrix[i][0]);
            dfs(matrix, candidate, i + 1);
            candidate.remove(candidate.size() - 1);
        }
    }
}
